1. Field of the Invention
The invention relates to an asynchronous time division multiplex (ATDM) switching system.
2. Description of Related Art
The function of an ATDM switch is to route packets of information, entering the switch via a number of input ports, through to output ports specified by header information contained within each packet and, in addition, to provide a queuing facility so that the switch can cope when packets on more than one input are destined for the same output. A simple method of implementing this function is to use a RAM, divided up into separate, fixed length queues, one for each output, together with some control logic that uses an incoming packet's header field to determine into which queue that packet should be stored. The output side of the switch simply takes packets from the tail end of each queue in turn and delivers them to the associated output port. The problem with this design is that it limits each queue to a fixed amount of space within the RAM, which under non-uniform traffic conditions, will prove inefficient as some queues fill up while others still have free space available. A better method is to construct the queues as chains of linked RAM locations which can expand into whatever areas of memory are still free. Here, locations in the same queue do not necessarily occupy contiguous locations in the RAM and so the system must store, for each location containing a packet--the address of the next location in that packer's queue, for each vacant location--the address of the next vacant location (these form their own queue, commonly known as the `Free List`) and for each queue--the address of the locations at the head and tail ends of that queue together with a count of the number of elements it contains. Using this arrangement the memory allocated to a given queue is now proportional to the amount of traffic that is destined for the output port associated with that queue. Unfortunately this design also presents a problem, namely that channels having relatively high traffic densities can fill the memory to the point where those with less traffic are left with little or no queue space at all. One solution would be to reserve a minimum amount of memory for each queue but this suffers from the same drawback as the original design in that there would be times when data was being lost from busier channels whilst space reserved in other parts of the RAM was empty and, therefore, theoretically available for use. What is needed is a design that gives channels with less traffic priority access to the memory if and when it becomes full.